package 排序;

import java.util.Arrays;

/** 归并排序
 * 主要思想：对已经排好序的两个数组，分而治之
 * Created by Administrator on 2017/8/29.
 * @Author jing
 */
public class MergeSort {
    public static void main(String args[]){
        int a[] = {2,4,11,8,1,3,5,9};
        int temp[]=new int[8]; //开辟数组空间，用来存放每次临时的
        mergesort(a,0,a.length-1,temp);
        System.out.println(Arrays.toString(a));
    }

    /**
     * @param a      要排序的数组
     * @param first  要排序数组的开始索引
     * @param last   要排序数组的结束索引
     * @param temp   存放两个有序数组的合并数组
     */
    //第一步：将数组打散成单个元素(视为有序的数组)
    public static void mergesort(int[] a, int first, int last, int[] temp)
    {
        if (first < last) //递归法，将一个数组打散成单独的元素(视为有序)
        {
            int mid = (first + last) / 2;
            mergesort(a, first, mid, temp); //左边有序
            mergesort(a, mid + 1, last, temp); //右边有序
            mergearray(a, first, mid, last, temp); //再将二个有序数列合并
        }
    }

    /**
     * @param a      要排序的数组
     * @param first  数组有序部分1：[first,mid]
     * @param mid
     * @param last   数组有序部分2：[mid+1,last]
     * @param temp   存放两个有序数组的合并数组
     */
    //第二步：将一个数组两部分有序的，合并成一个完成的有序部分
    public static void mergearray(int[] a, int first, int mid, int last, int temp[])
    {
        int f = first, m = mid; //有序部分1：[first,mid]
        int j = mid + 1, l = last; //有序部分2：[mid+1,last]
        int k = 0;     //临时完整有序数组的索引
        while (f <= m && j <= l)  //在有序数组部分时
        {
            if (a[f] <= a[j])  //每次将较小的部分放到新数组
                temp[k++] = a[f++];
            else
                temp[k++] = a[j++];
        }
        while (f <= m) temp[k++] = a[f++]; //必定是有一个部分数组的元素，先全部放到新数组，所以要将剩余大的全部转移到新数组
        while (j <= l) temp[k++] = a[j++];
        for (int i = 0; i < k; i++) //将临时数组完整有序的部分，赋值到原始数组中
            a[first + i] = temp[i];
    }
}

/*
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应
数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
//C语言代码：将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
    int i, j, k;

    i = j = k = 0;
    while (i < n && j < m) //比较两个有序数组，将小的部分全部插入到新的数组中
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }

    while (i < n) //将剩下的部分大可能没有插入的，继续插入到新数组
        c[k++] = a[i++];

    while (j < m) //将剩下的部分大可能没有插入的，继续插入到新数组
        c[k++] = b[j++];
}
可以看出合并有序数列的效率是比较高的，可以达到O(n)。

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，
那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，
然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序
 */